package practise.alogrithm;


import practise.alogrithm.introductionToAlogrithm.LinkedListBuilder;
import practise.alogrithm.introductionToAlogrithm.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by Richard on 7/28/2014.
 */
public class ReorderLink {
    public ListNode<Character> reorder(ListNode<Character> listNode, List<Character> charOrders){
        //init
        ListNode<Character> changePointer = listNode;
        ListNode<Character> listHead = listNode;
        int index=1;
        //init move to the second charactor
        for(;changePointer.getNext().getValue()!=charOrders.get(1);changePointer=changePointer.getNext());
        //start to change
        while(changePointer.getNext()!=null&&index<charOrders.size()){
            listHead=listNode;
            for(;listHead.getNext().getValue()!=charOrders.get(0);listHead=listHead.getNext());
            while(index<charOrders.size()&&changePointer.getNext().getValue()==charOrders.get(index)){

                ListNode<Character> firstNext = listHead.getNext();
                ListNode<Character> secondNext = changePointer.getNext().getNext();
                listHead.setNext(changePointer.getNext());
                changePointer.setNext(secondNext);
                listHead = listHead.getNext();
                listHead.setNext(firstNext);
                listHead=listHead.getNext();
                if(changePointer==firstNext){
                    changePointer=changePointer.getNext();
                    break;
                }
                for(;listHead!=null&&listHead.getNext()!=null&&listHead.getNext().getValue()!=charOrders.get(0);listHead=listHead.getNext());

            }
            index++;
        }
        return listNode;
    }

    public static void main(String[] args){
        ListNode<Character> characterListNode = LinkedListBuilder.buildLinkedListFromArray(new Character[]{'r','r','r','r','g','g','g','g','y','y','y','y','b','b','b','b'});
        ReorderLink reorderLink = new ReorderLink();
        reorderLink.reorder(characterListNode,new ArrayList<Character>(Arrays.asList(new Character[]{'r','g','y','b'})));
        while(characterListNode!=null){
            System.out.print(characterListNode.getValue()+":");
            characterListNode=characterListNode.getNext();
        }
    }
}
